package com.henry.base.sort;

import java.util.*;

public class BigSort {
    private int[] a;//数组存储元素的数组
    private int BIT_LENGTH=32;//位数，默认使用int
    private int P; //整数部分
    private int S;//余数部分
    private int MASK = 0x1F; //2^5-1
    private int SHIFT = 5 ;//移位  2^5=32


    public void set(int i) {
        P=i>>SHIFT;//结果等同  P=i/BIT_LENGTH
        S=i&MASK;//结果等同  S=i%BIT_LENGTH

        a[P]  |= 1<<S; //赋值设置该元素对应的bit位为1 (把从右往左第S+1位设置为1)
//        a[P] &= ~(1<<S);//把从右往左第S+1位设置为0

//        a[i >> SHIFT] |= (1 << (i & MASK));
    }

    public void bit2Integer(int[] a) {
        for (int i = 0; i < a.length; i++) {
            if(a[i]!=0){
                for (int j = 0; j < BIT_LENGTH; j++) {
                    //a[i]右移j位  再 &1  如果=1  说明从右往左第j+1位有数
                    if (((a[i] >> j) & 0x01) == 1) {
                        System.out.println((i<<5)+j);
                        //此处输出的就是排好序的数字，正常来讲此处可以往一个队列里面不停地放
                        //有点类似disruptor的思想  不停地进，不停地出，处理的核心逻辑用超高效的单线程代码实现
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Random random = new Random();
        List<Integer> list = new ArrayList<>();
        int max = 800000;

        for (int i = 0; i < max; i++) {
//            int x = random.nextInt(3);
//            if (x >= 0)
                list.add(i);
        }
        System.out.println(list.size());
//        System.out.println(list.toString());
        Collections.shuffle(list);
//        System.out.println(list.toString());

        long beg1 = System.nanoTime();
        Collections.sort(list);
        long end1 = System.nanoTime();

        Collections.shuffle(list);


        BigSort bigSort = new BigSort();
        bigSort.a = new int[max/32+1];

        long beg2 = System.nanoTime();

        for (Integer integer : list) {
            bigSort.set(integer);
        }
        long end2 = System.nanoTime();


        System.out.println((end1-beg1)/1000/1000);
        System.out.println((end2-beg2)/1000/1000);

//        System.out.println(Arrays.toString(bigSort.a));
//        bigSort.bit2Integer(bigSort.a);



    }

}
